#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
#include <cassert>

using namespace std;

#define N 4
#define N2 16
#define LIMIT 1000                                  // 代表你设置的最大限度
int MDT[N2][N2];                                    // 代表所有节点的曼哈顿距离数组
static const int dx[4] = { 0,-1,0,1 };              // 方向数组
static const int dy[4] = { 1,0,-1,0 };              // 方向数组
static const char dir[4] = { 'r','u','l','d' };     // 代表移动的标识，当搜索到最优解时，通常通过移动的标识长度来计算步数，
                                                    // 同时也可以根据该标识来从输入的拼图推出最终的拼图。(r为向右，l为向左，u为向上，d为向下)
struct Puzzle {                                     // 代表拼图的结构体
    int f[N2];                                      // 代表当前的拼图
    int space;                                      // 代表空位的下标(或者说是0拼图下标)
    int MD;                                         // 代表当前拼图的曼哈顿距离
};

Puzzle state;                                       // 声明一个拼图(用处之后再说)

int limit;                                          // 代表最小成本的变量limit，也是IDA*中不断增加的限制值，
                                                    // 在本题中起始值通常为输入拼图的曼哈顿距离，
                                                    // 限制值一直增加到你设定的最大值LIMIT为止。
                                                    // 若你的限定值limit在增加时超过了最大值，但还是没有搜索出结果的话，结果就为unsolvable

int path[LIMIT];                                    // 代表存储搜索到的路径数组。（也就是说，当你找到了从输入拼图到最终拼图的最短路径，
                                                    // 那么在本题中这个路径会以一串移动的标识来显示。决定移动标识的下标值就会存储在这个路径数组中。

int getAllMD(Puzzle pz)                             // 代表求出输入拼图的曼哈顿距离的函数
{
    int sum = 0;                                    // 代表各个拼图的曼哈顿距离之和就为输入拼图的曼哈顿距离
    for (int i = 0; i < N2; i++)
    {
        if (pz.f[i] == N2)                          // 如果进行遍历的拼图为空位，那么就直接进行返回。因为空位不算拼图，因此没有曼哈顿距离
        {
            continue;
        }
        sum += MDT[i][pz.f[i] - 1];                 // 通过这个式子来算出各个拼图的曼哈顿距离，并进行相加
    }
    return sum;                                     // 返回输入拼图的曼哈顿距离
}

bool isSolved() {                                   // 这个isSolved函数就是代表检测输入的拼图是否能有还原到最终拼图的可能。
    for (int i = 0; i < N2; i++)
    {
        if (state.f[i] != i + 1)                    // 判断移动之后的各个拼图跟最终的各个拼图相比是否一样
        {
            return false;                           // 如果有一个拼图不一样，则移动之后的拼图跟最终拼图肯定就不一样了
        }
    }
    return true;                                    // 如果拼图都一样，则移动之后的拼图跟最终拼图也就一样了。
}

bool dfs(int depth, int prev)                       // 代表dfs函数，其中depth代表当前深度，prev代表进行传入的移动下标(r)
{
    if (state.MD == 0)                              // 如果刚开始搜索时曼哈顿距离就为0，则代表输入拼图=最终拼图，那么不用向下遍历，直接返回true
    {
        return true;
    }
    if (depth + state.MD > limit)                   // 如果当前的搜索深度+当前拼图的启发值（曼哈顿距离) 大于限制深度的话，
                                                    // 我们就要对其进行剪枝，禁止dfs再向下搜索。
    {
        return false;
    }
    int sx = state.space / N;                       // 根据这个式子来求出当前所在的坐标(sx,sy),老实说我也没明白这个式子是什么意思，
                                                    // 但是我们可以暂时理解为就是当前空位的下标，之后我们要对这个空位来进行移动，从而得到拼图的不同情况。
    int sy = state.space % N;
    Puzzle tmp;                                     // 声明拼图tmp
    for (int r = 0; r < 4; r++)
    {
        int tx = sx + dx[r];                            // 将当前空位进行上下左右四个方向的移动，得到新坐标(tx,ty)
        int ty = sy + dy[r];
        if (tx < 0 || ty < 0 || tx >= N || ty >= N)     // 如果移动的下标要是越界的话，就直接进行返回
        {
            continue;
        }

        if (max(prev, r) - min(prev, r) == 2)           // 这个式子非常重要，虽说我是不知道它怎么来的，但是这个式子的意思是避免重复的搜索，
        {                                               // 如果有重复的搜索就直接返回。（例如：我将输入拼图中的8向右移动了一次，
            continue;                                   // 那么拼图为:1 2 3 4 6 7 16 8 5 10 11 12 9 13 14 15。将移动之后的地图进行再次的dfs，
        }                                               // 那么再次dfs的话，就有可能出现将8再向左移动一位的情况。
                                                        // 向左移动一位的话，拼图就又变回去了(1 2 3 4 6 7 8 16 5 10 11 12 9 13 14 15)。
                                                        // 所以，为了防止这个情况的发生，有了这个式子。(不信的话可以打个断点，试一下就知道了。)

        tmp = state;                                                // 将temp地图等于state拼图
        state.MD -= MDT[tx * N + ty][state.f[tx * N + ty] - 1];     // 代表进行拼图的移动时，有没有因为这个拼图的移动导致原先的曼哈顿距离减少。
                                                                    // 典型的例子就是将拼图移动到了规定的位置中(这里规定的位置指某块拼图在终点拼图的位置)。
                                                                    // 并且，这段话的意思就是计算移动后的新拼图的曼哈顿距离

        state.MD += MDT[sx * N + sy][state.f[tx * N + ty] - 1];     // 代表进行拼图的移动时，有没有因为这个拼图的移动导致原先的曼哈顿距离增加。
                                                                    // 典型的例子就是某块拼图移动到了规定的位置更远处。
                                                                    // （举个例子：例如我将输入拼图1 2 3 4 6 7 8 16 5 10 11 12 9 13 14 15 中的4向下移动，
                                                                    // 那么原先的曼哈顿距离就会加1。（因为4向下移动并没有将原来的曼哈顿距离减少，
                                                                    // 因为除4之外的拼图都没有进行移动。而4向下移动就会让4脱离原先正确的位置，
                                                                    // 使原先的曼哈顿距离加了1)

        swap(state.f[tx * N + ty], state.f[sx * N + sy]);   // 代表进行拼图的移动，并生成新拼图state
        state.space = tx * N + ty;                          // 重新计算新拼图的空位下标
        if (dfs(depth + 1, r))                              // 生成新拼图后向下继续搜索
        {
            path[depth] = r;                        // 如果搜索成功，那么就将最短步数中的每一步都记录在path数组中。
                                                    // r代表移动的具体方向下标。depth代表当前遍历的深度。其实就是第几步的意思。
                                                    // (例如：path[5] = 2，就代表第5步向左移动的意思,同时对应着移动标识的'l')
            return true;                            // 代表搜索成功，返回上一层
        }
        state = tmp;                                // 如果在这个拼图的移动中，搜索没成功的话，那么就将当前移动之后的拼图
                                                    // 回溯到之前没有进行移动过的状态，并尝试进行下一方向的移动。
    }
    return false;                                   // 如果四个方向搜索均没有成功的话，那么就代表当前限制深度(limit)中无解，
                                                    // 需要在下一个限制深度(limit+1)中重新进行dfs。
}

string iterative_deepening(Puzzle in)               // 代表进行IDA*搜索的函数
{
    in.MD = getAllMD(in);                           // 计算输入拼图的启发值,同时也是输入拼图的曼哈顿距离
    for (limit = in.MD; limit <= LIMIT; limit++)    // 进行迭代加深搜索的循环，起始限制值为输入拼图的曼哈顿距离(启发值)，
                                                    // 通过不断搜索增加限制值，实其让dfs具有bfs的功能。直到限制值增大到最大值（LIMIT)+1为止。
                                                    // 如果限制值一直到最大值+1的期间都没有搜索到结果，则整个IDA*也就无法找到结果。
    {
        state = in;                                 // 把输入拼图赋值到state拼图中
        if (dfs(0, -100))                           // 进行dfs搜索（实际上IDA*就是比dfs增加了最大搜索深度(限制值limit),
                                                    // 通过这个最大搜索深度，我们就能让dfs具有bfs的功能，
                                                    // 但代价是每次循环(加大深度时)都得需要将之前搜索过的深度再次搜索一遍)。
                                                    // 除了这个之外，就跟普通的dfs没有什么区别。
        {
            string ans = "";                        // 声明移动的标识(当dfs找到最短路径时(dfs的返回值为true))
            for (int i = 0; i < limit; i++)         // 如果找到了最短步数，那么这个最短步数的值一定等于当前的限制深度(limit)，
            {                                       // 因为初始limit变量值为输入地图的曼哈顿距离。
                                                    // （那也就代表了当前拼图至少得移动limit步才能移动到最终的拼图)因为每增加一层深度，
                                                    // 就代表多走一个步数，因此若搜索出来了最短步数，那么这个最短步数一定跟当前的限制深度相等。

                ans += dir[path[i]];                // 根据遍历的下标(i)求出移动标识的下标(path[i]),根据移动标识的下标求出移动标识(dir[path[i]])
            }
            return ans;                             // 返回移动的标识
        }
    }
    return "unsolvable";                            // 如果说一直加深的限定值超过了最大值但还是没有搜索到结果，那么就返回unsolvable
}

int main()
{
    int i, j;
    for (i = 0; i < N2; i++)
    {
        for (j = 0; j < N2; j++)
        {
            MDT[i][j] = abs(i / N - j / N) + abs(i % N - j % N);    // 根据这个式子来计算所有拼图(0-15)分别在所有位置(0-15)上的曼哈顿距离
                                                                    // (PS：这个式子是怎么得到的，本人也不是太清楚。不得不说，想出这个式子的人真的很厉害！)
        }
    }
    Puzzle in;                                                      // 声明一个拼图(输入拼图)
    for (i = 0; i < N2; i++)
    {
        cin >> in.f[i];                                             // 进行拼图的输入
        if (in.f[i] == 0)                                           // 如果输入的是空位(0拼图)
        {
            in.f[i] = N2;                                           // 将这个空位的值标识为16(则整个拼图为:1-16 其中，16为空位置)
            in.space = i;                                           // 记录一下空位的位置(下标值)
        }
    }
    string  ans = iterative_deepening(in);                          // 进行IDA*搜索,其中ans代表移动的标识(为一串字母)
    cout << ans.size() << endl;                                     // 计算标识长度(就是输入拼图还原到原拼图的最短步数)

    return 0;
}
